1. Field of the Invention
The invention relates generally to the field of computer networks comprising a plurality of stations which communicate data in a ring using a token-based protocol and more specifically to a mechanism for removing extraneous or erroneous data or ring control information from the network.
2. Description of the Prior Art
A computer network enables various devices, such as processors, mass storage devices, and printers, to communicate with each other over high speed communication links. The devices are connected, that is, coupled, to the network, and thus transfer data to and from the network through stations. The stations are interconnected by the communication links.
One example of such a network is a Local Area Network (LAN). A LAN allows high-bandwidth communication among devices within a limited geographic area. The communication links are typically composed of fiber optics, coaxial cable or twisted conductor pairs.
LAN's may be configured as rings, with network stations transmitting data in one direction around the ring. Thus when a station transmits data onto the ring, the data travels around the ring from station to station, with each station receiving the data from the preceding station and repeating it to the succeeding station, until the data reaches the station that is to receive it. In a well-known ring network the receiving, or destination, station also repeats the data to its downstream successor and the data thus continues around the ring to the originating, or source, station.
The stations operate in accordance with communication protocols which facilitate the orderly transfer of data over the communication links. One type of communication protocol is a token-ring system. Such systems use a token, that is, a specific string of bits, to indicate that a transmitting station has completed its transmission. A succeeding station may then, following the dictates of the protocol, begin transmitting data upon receipt of the token.
In a token-ring system a station may not transmit data over the ring unless it actually holds the token. Thus if a station has data to transmit around the ring, it removes the token from the ring data stream, that is, it "captures" the token, when it receives it from the preceding station. The capturing station then begins its data transmission. When the station is finished with the data transmission it retransmits the token, effectively releasing it. The succeeding stations thereafter transfer the token around the ring until a station captures it in order to make another transmission.
Network stations transmit and receive data in the form of frames. The frames contain, in addition to the data, addresses, an error detection sequence and status flags, for example, a flag indicating receipt of the frame by the intended receiving, or destination, station. The frame addresses identify the source station and destination station or stations.
Every station and every attached device is identified by a unique address. Thus each station has associated with it its unique station-address and the addresses of its attached devices. The stations may have other addresses, for example, logical addresses, associated with them, also. A frame directed from a source station to a single destination station thus contains the address of the source station and, for example, the address of a specific device attached to the destination station. Each station may maintain a list of its associated addresses, such that the station receives the frames containing any one of its addresses.
A destination station, in addition to repeating the frame to its succeeding station, copies the frame for use by the appropriate device(s) associated with the station. The destination station may also set the applicable status flags indicating receipt of the frame.
When the frame has returned to the source station, the station, recognizing the frame as its own, for example, by recognizing the source address in the frame as its own, removes, or strips, the frame from the ring data stream. After a transmission, the first frames received by the source station over the ring are the frames it transmitted, assuming proper operation of the stations on the ring.
Frames may be altered as they travel around the ring. The alteration may affect the source addresses in a number of frames, rendering them unrecognizable to the source stations. The source stations will not then strip the frames, and these frames will travel continuously around the ring. Thus a station listed as a destination station will repeatedly receive and process the frames. The processing will ordinarily detect the duplication, but it does require the use of station resources that might conflict with or delay other operations of the station.
A similar situation occurs when a station which has transmitted frames on to the ring becomes inoperative before it strips the transmitted frames. These frames, like the frames with altered source addresses, continuously travel around the ring because none of the stations then operating on the ring recognize the frames as their own and strip them. Accordingly, these frames, the altered-address frames and any other frames continuously traversing the ring are commonly referred to as "no-owner" frames. No-owner frames needlessly take up ring bandwidth by continuously traveling around the ring. These frames may also cause processing backlogs in the destination stations because the stations must process them each time they receive them. The no-owner frames often require frequent and fast processing because they return to the destination stations in the time it takes the frames to traverse the ring, which is typically faster than frames are ordinarily received. Thus it is desirable to rid the ring of no-owner frames.
A mechanism to purge no-owner frames from rings operating under the IEEE 802.5 standard protocol involves stripping all data from the ring, and then re-initializing the ring. Re-initializing the ring causes it to perform all actions necessary to re-start the ring and make it operational. For example, the initialization includes a claim token operation and the creation of a new token. The claim token operation involves an arbitration process during which the winner of the arbitration, also called the claim token winner, creates the new token. Ring re-initialization may take a considerable period of time and result in lost performance during this period. Thus, for performance considerations, ring re-initializations should be performed as infrequently as possible.
To detect a no-owner frame, that is, to determine when a ring re-initialization is necessary, a station, referred to in the IEEE 802.5 standard protocol as an Active Monitor, places a marker at the beginning of each frame it repeats over the ring. If the Active Monitor thereafter detects a frame containing a marker, indicating that the frame traveled completely around the ring without being stripped, it begins a purge operation which includes a ring re-initialization. The marker is not protected by the frame error detection sequence. Thus an error in the marker may either start a purging operation unnecessarily or prevent one from occurring.
A purge operation begins with the Active Monitor placing a purge frame on the ring and then stripping everything off the ring that it receives. The Active Monitor may transmit multiple purge frames or it may transmit idle frames to fill the ring while it continues stripping everything, including the token, from the ring. When the Active Monitor receives one of its purge frames, indicating that it has essentially filled the ring with the purge and idle frames, it re-initializes the ring and issues a new token. Thus each purge operation causes the loss of all data then on the ring. There is a need for an improved purge mechanism which minimizes the loss of data on the ring and which does not require ring re-initialization and/or ring operation interruption.
The purge operation described above may be used only with ring protocols which allow markers to be placed at the beginning of a frame, for example, the IEEE 802.5 protocol At the present time, protocols such as the ANSI Fiber Distributed Data Interface (FDDI) protocol which do not allow frame markers at the start of frames do not have any mechanism to handle no-owner frames. Thus a purge mechanism which may be used with any token-ring protocol and/or frame format is desirable.
Every time a ring is initialized, a station must be designated as the ring purging station. If the ring is operating according to the IEEE 802.5 protocol the same station, i.e., the Active Monitor, is designated the ring purger after each ring initialization. If the Active Monitor station later fails or is otherwise removed from the ring, the ring must operate without a ring purger until after the ring is initialized. Thus there is a need for an improved mechanism to select a ring purging station. The mechanism should operate after each ring initialization. It should also operate between initializations whenever a previously operating ring purger becomes inoperative.
Token rings may occasionally experience an error condition in which multiple tokens are simultaneously traveling around the ring. This condition may result in multiple stations simultaneously transmitting data onto the ring. If a station which is transmitting receives data frames over the ring, it removes them. Thus data frames transmitted by one station may be removed by a second transmitting station. If the frames are removed before they reach the intended destination, ring operations may be disrupted and data may be lost. Normal operations of the ring may correct the multiple token condition, for example, the second token may be removed by a transmitting station. However, if the multiple token error condition persists, other protocol operations may also be affected, and ring operations may be significantly disrupted. Neither the IEEE 802.5 protocol nor the ANSI FDDI protocol has any mechanism for the detection of a multiple token error condition. Thus the condition will go unchecked until the amount of data which is lost disrupts the operation of the ring enough to cause a ring initialization. Accordingly, there is a need for a mechanism which deterministically detects multiple tokens on the ring.